package 数据结构和算法.剑指offer.递归和循环.斐波那契数列.青蛙跳台阶问题;

/**
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
 * 如果n=1，只有一种跳法，那就是1
 * 如果n=2，那么有两种跳法，2，[1,1]
 * 如果n=3，那么有三种跳法，[1,1,1],,[1,2],[2,1]
 * 如果n=4，那么有五种跳法，[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]
 * 如果n=5，那么有八种跳法，[1,1,1,1,1],[1,1,1,2],[1,1,2,1],[1,2,1,1],[2,1,1,1],[2,2,1],[2,1,2],[1,2,2]
 * 结果为1，2，3，5，8  这不特么是斐波那切数列嘛
 */
public class Test {
    public static void main(String[] args) {

    }

    // 递归做法
    public static int jump1(int n) {
        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }

        return (jump1(n - 1) + jump1(n - 2));
    }

    public static int jump2(int n) {
        int a = 0;
        int b = 1;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum = a + b;
            a = b;
            b = sum;
        }

        return a;
    }
}
